package com.ma.graph;

import java.util.*;

/*
 * 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
 * 输出：[0,2,1,3]
 * 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
 * 因此，一个正确的课程顺序是[0,1,2,3] 。另一个正确的排序是[0,2,1,3]
 */
public class Solution210 {

    List<Integer> postorder = new ArrayList<>();
    boolean[] isVisited;
    boolean[] onPath;
    boolean hasCycle = false;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGroup(numCourses, prerequisites);
        isVisited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        for(int i = 0;i<numCourses;i++){
            if(!isVisited[i]){
                traverse(graph,i);
            }
        }
        if(hasCycle){
            return new int[]{};
        }
        Collections.reverse(postorder);
        int[] res = new int[numCourses];
        for(int i = 0;i< numCourses; i++){
            res[i] = postorder.get(i);
        }
        return res;
    }

    private void traverse(List<Integer>[] graph, int s) {
        if(onPath[s]){
            hasCycle = true;
        }
        if(hasCycle||isVisited[s]){
            return;
        }
        isVisited[s] =true;
        onPath[s] = true;
        for(int t : graph[s]){
            traverse(graph,t);
        }
        postorder.add(s);
        onPath[s] = false;
    }


    List<Integer>[] buildGroup(int numCourses, int[][] prerequisites){
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int i = 0; i < numCourses; i++){
            graph[i] = new LinkedList<>();
        }
        for(int[] edge:prerequisites){
            int from = edge[1];
            int to = edge[0];
            graph[from].add(to);
        }
        return graph;

    }
    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0},{3,1},{3,2}};

         //输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
         //输出：[0,2,1,3]
        Solution210 solution = new Solution210();
        int[] order = solution.findOrder(numCourses, prerequisites);
        for(int i = 0; i < order.length; i++){
            System.out.println(order[i]);
        }
    }
}
